public class Test {
    //JZ6 从尾到头打印链表
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //可以设置每次从顺序表的0下标位置插入，得到的就是逆序
        ArrayList<Integer> list = new ArrayList<>();
        ListNode cur = listNode;
        while(cur != null){
            list.add(0,cur.val);
            cur = cur.next;
        }
        return list;
    }
    //JZ24 反转链表
    public ListNode ReverseList(ListNode head) {
        //通过辅助栈来反转
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        //入栈
        while(cur != null){
            stack.push(cur.val);
            cur = cur.next;
        }
        //出栈进入链表
        cur = head;
        while(!stack.isEmpty()){
            cur.val = stack.pop();
            cur = cur.next;
        }
        return head;
    }
    //JZ24 反转链表 每次头插
    public ListNode ReverseList(ListNode head) {
        ListNode list = null;
        ListNode listHead = null;
        ListNode cur = head;
        //每次头插
        while(cur != null){
            if(listHead == null){
                list = new ListNode(cur.val);
                listHead = list;
            }else{
                listHead = new ListNode(cur.val);
                listHead.next = list;
                list = listHead;
            }
            cur = cur.next;
        }
        return listHead;
    }
    //JZ25 合并两个排序的链表
    public ListNode Merge(ListNode list1,ListNode list2) {
        //严防有一方为空
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode start1 = list1;
        ListNode start2 = list2;
        ListNode head = null;
        ListNode cur = null;
        ListNode pd = null;
        //有一方为空就停下来
        while(start1 != null && start2 != null){
            if(start1.val < start2.val){
                if(head == null){
                    head = new ListNode(start1.val);
                    cur = head;
                    pd = head;
                }else{
                    cur = new ListNode(start1.val);
                    pd.next = cur;
                    pd = cur;
                }
                start1 = start1.next;
            }else{
                if(head == null){
                    head = new ListNode(start2.val);
                    cur = head;
                    pd = head;
                }else{
                    cur = new ListNode(start2.val);
                    pd.next = cur;
                    pd = cur;
                }
                start2 = start2.next;
            }
        }
        //检测还有哪一方没有完
        if(start1 != null){
            cur.next = start1;
        }
        if(start2 != null){
            cur.next = start2;
        }
        return head;
    }
    //优化空间复杂度O(1)
    public ListNode Merge(ListNode list1,ListNode list2) {
        //优化空间复杂度为O(1)
        ListNode head = new ListNode(-1);//虚拟结点
        ListNode cur = head;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                cur.next = list1;
                cur = list1;
                list1 = list1.next;
            }else{
                cur.next = list2;
                cur = list2;
                list2 = list2.next;
            }
        }
        if(list1 != null){
            cur.next = list1;
        }
        if(list2 != null){
            cur.next = list2;
        }
        return head.next;
    }
    //JZ52 两个链表的第一个公共结点
    public ListNode FindFirstCommonNode(ListNode head1, ListNode head2) {
        if(head1 == null && head2 == null){
            return null;
        }
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        int count1 = 0;
        int count2 = 0;
        //先求出链表的长度差
        while(cur1 != null){
            count1++;
            cur1 = cur1.next;
        }
        while(cur2 != null){
            count2++;
            cur2 = cur2.next;
        }
        //比较大小，谁长谁就先走长度的差值,使其同步
        cur1 = head1;
        cur2 = head2;
        if(count1 > count2){
            int D_value = count1 - count2;
            while(D_value > 0){
                D_value--;
                cur1 = cur1.next;
            }
        }else{
            int D_value = count2 - count1;
            while(D_value > 0){
                D_value--;
                cur2 = cur2.next;
            }
        }
        //同步后两个一起走,相遇后停下,cur1 == null是防止对null解引用，并且说明没有公共结点
        while(cur1 != null && cur1.val != cur2.val){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        //若为空说明没有公共点
        if(cur1 == null){
            return null;
        }else{
            return cur1;
        }
    }
    //JZ23 链表中环的入口结点
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        Set<Integer> set = new HashSet();
        ListNode cur = pHead;
        while(cur != null){
            //一旦发现重复，立刻返回
            if(set.contains(cur.val)){
                return cur;
            }
            set.add(cur.val);
            cur = cur.next;
        }
        return null;
    }
    //JZ22 链表中倒数最后k个结点
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null){
            return null;
        }
        int count = 0;
        ListNode cur = pHead;
        //计数
        while(cur != null){
            count++;
            cur = cur.next;
        }
        cur = pHead;
        //求差值,确定走的步数
        int D_value = count - k;
        if(D_value < 0){
            return null;
        }
        while(D_value > 0){
            D_value--;
            cur = cur.next;
        }
        return cur;
    }
    //JZ22 链表中倒数最后k个结点(快慢指针法)
    public ListNode FindKthToTail (ListNode pHead, int k) {
        if(pHead == null){
            return null;
        }
        ListNode fast = pHead;
        ListNode slow = pHead;
        //快指针先走k步
        while(k > 0 && fast != null){
            k--;
            fast = fast.next;
        }
        //严防K值大于链表长度
        if(k > 0 && fast == null){
            return null;
        }
        //快慢指针一起走,fast为空时，返回即可
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
    //JZ35 复杂链表的复制
    public RandomListNode Clone(RandomListNode pHead) {
        //通过HashMap来确定随机指针
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        //虚拟头结点
        RandomListNode head = new RandomListNode(-1);
        RandomListNode cur = head;
        //拷贝val值，并创建新链表
        RandomListNode pCur = pHead;
        while(pCur != null){
            cur.next = new RandomListNode(pCur.label);
            cur = cur.next;
            map.put(pCur, cur);
            pCur = pCur.next;
        }
        cur = head.next;
        pCur = pHead;
        //随机指针的复制
        while(pCur != null){
            cur.random = map.get(pCur.random);
            pCur = pCur.next;
            cur = cur.next;
        }
        return head.next;
    }
    //JZ76 删除链表中重复的结点
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        //创建一个虚拟头节点
        ListNode head = new ListNode(-1);
        head.next = pHead;
        ListNode cur = pHead;
        ListNode prev = head;
        ListNode prevPrev = null;
        while(cur != null){
            //找到了
            if(prev.val == cur.val){
                //继续找有没有重复的
                while(cur != null && prev.val == cur.val){
                    cur = cur.next;
                }
                if(cur == null){
                    prevPrev.next = null;
                    return head.next;
                }else{
                    prevPrev.next = cur;
                    prev = cur;
                    cur = cur.next;
                }
            }else{
                prevPrev = prev;
                prev = cur;
                cur = cur.next;
            }
        }
        return head.next;
    }
    //JZ76 删除链表中重复的结点(单指针优化)
    public ListNode deleteDuplication(ListNode pHead) {
        if(pHead == null){
            return null;
        }
        //创建一个虚拟头节点
        ListNode head = new ListNode(-1);
        head.next = pHead;
        ListNode cur = head;
        while(cur.next != null && cur.next.next != null){
            //发现重复
            if(cur.next.val == cur.next.next.val){
                int tmp = cur.next.val;
                //继续向后找出所有相同的，注意while条件的先后顺序不能变
                while(cur.next != null && cur.next.val == tmp){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return head.next;
    }
}
